1. Field of the Invention
This application relates to motion estimation in digital video. In particular, this application relates to systems and methods which determine an adaptive vertical search range used to provide motion estimation in digital video content.
2. Description of the Related Technology
In recent years, advancements in digital video processing have allowed video display manufacturers to produce systems which provide a more realistic viewing experience by enhancing raw digital video. Motion estimation algorithms are commonly used in providing enhanced video. For example, motion estimation algorithms are often utilized when performing de-interlacing of video, video format conversion, and frame rate conversion. Among the different types of motion estimation algorithms, block matching algorithms are often chosen for their superior trade-off between complexity (which is relatively low) and accuracy (which tends to be high). Block matching algorithms generally compare a given arbitrary block in one frame of video to one or more blocks from another frame of video in order to find a suitable matching block.
There are various different block matching algorithms which may be implemented to provide motion estimation. For example, full search algorithms, three-step search algorithms, four-step search algorithms, and recursive algorithms may all be used to provide motion estimation. Providing high quality block matching is often dependent on selecting an appropriate search range. A search range may be defined as a rectangular area having a horizontal search range and a vertical search range. For example, a search range may be defined as [−64,64] by [−16,16] to indicate that a motion vector may be obtained ranging from −64 to 64 units in the horizontal direction and −16 to 16 units in the vertical direction. In order to track a motion vector, the search range generally needs to be as large as the largest anticipated motion vector. Thus, larger motion vectors generally require larger search ranges. Increasing the size of a search range typically increases both the computational complexity and the hardware cost of the motion estimation process because there must typically be enough memory available to store all pixel values for the entire search range. Although various techniques to save computational complexity or hardware cost in motion estimation systems have been proposed, these techniques are not adequate.